package solutions.leetcode.easy;

import solutions.lib.BaseSolution;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/minimum-subsequence-in-non-increasing-order/">1403. 非递增顺序的最小子序列</a>
 */
public class Solution1403 extends BaseSolution {

    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums);
        List<Integer> rst = new LinkedList<>();
        int sum = 0;
        for (int v : nums) {
            sum += v;
        }
        int ts = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            rst.add(nums[i]);
            ts += nums[i];
            if (ts * 2 > sum) {
                break;
            }
        }
        return rst;
    }

    public static void main(String[] args) {
        Solution1403 solution = new Solution1403();
        printVals(solution.minSubsequence(new int[] {
                4,3,10,9,8
        }));
    }
}